#!/usr/bin/env python3

"""
解决数独问题
"""

class Solution:
    DIGITS = [str(item) for item in range(1, 10)]
    
    def solve_sudoku(self, board):
        digits_maps = {}
        for row_index, row in enumerate(board):
            for column_index, ch in enumerate(row):
                sub_box_index = int(row_index / 3) * 3 + int(column_index / 3)
                if ch == '.':
                    continue
                if ch in digits_maps:
                    row_set, column_set, sub_box_set = digits_maps[ch]
                    row_set.add(row_index)
                    column_set.add(column_index)
                    sub_box_set.add(sub_box_index)
                else:
                    digits_maps[ch] = ({row_index}, {column_index}, {sub_box_index})

        self._solve_sudoku(board, digits_maps)

    def _solve_sudoku(self, board, digits_maps):
        for row_index, row in enumerate(board):
            for column_index, ch in enumerate(row):
                if ch != '.':
                    continue
                sub_box_index = int(row_index / 3) * 3 + int(column_index / 3)
                for ch in Solution.DIGITS:
                    if ch in digits_maps:
                        row_set, column_set, sub_box_set = digits_maps[ch]
                        if row_index in row_set or column_index in column_set \
                           or sub_box_index in sub_box_set:
                            is_valid_sudoku = False
                        else:
                            row_set.add(row_index)
                            column_set.add(column_index)
                            sub_box_set.add(sub_box_index)
                            is_valid_sudoku = True
                    else:
                        is_valid_sudoku = True
                        digits_maps[ch] = ({row_index}, {column_index}, {sub_box_index})
                    if not is_valid_sudoku:
                        continue
                    row[column_index] = ch
                    is_valid_sudoku = self._solve_sudoku(board, digits_maps)
                    if is_valid_sudoku:
                        return True
                    row[column_index] = '.'
                    row_set, column_set, sub_box_set = digits_maps[ch]
                    row_set.remove(row_index)
                    column_set.remove(column_index)
                    sub_box_set.remove(sub_box_index)
                else:
                    return False
        return True

    
if __name__ == '__main__':
    input = [
        ['5', '3', '.', '.', '7', '.', '.', '.', '.'],
        ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
        ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
        ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
        ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
        ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
        ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
        ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
        ['.', '.', '.', '.', '8', '.', '.', '7', '9']
    ]
    solution = Solution()
    solution.solve_sudoku(input)
    print(str(input))
